package anthology.daily_question._24_11;
//https://leetcode.cn/problems/shortest-distance-after-road-addition-queries-ii/description/?envType=daily-question&envId=2024-11-20
public class _3244新增道路查询后的最短距离2 {
    class Solution {
        public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
            int[] roads = new int[n];
            for (int i = 0; i < n; i++) {
                roads[i] = i + 1;
            }
            int[] res = new int[queries.length];
            int dist = n - 1;
            for (int i = 0; i < queries.length; i++) {
                int k = roads[queries[i][0]];
                roads[queries[i][0]] = queries[i][1];
                while (k != -1 && k < queries[i][1]) {
                    int t = roads[k];
                    roads[k] = -1;
                    k = t;
                    dist--;
                }
                res[i] = dist;
            }
            return res;
        }
    }
}
